package test_34;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张杰
 * Date: 2022-03-04
 * Time: 16:17
 */
class TreeNode{
    TreeNode left;
    TreeNode right;
    int value;
    TreeNode(int value){
        this.value = value;
    }
}
public class BinaryTree {
    private TreeNode root;
    public TreeNode createBinaryTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
        return root;
    }

    /* 求二叉树节点个数
     * @author zj
     * @date 2022/3/2
     * @param null
     * @return null
     */
    //1、遍历二叉树的节点个数(遍历的思路)
    int count = 0;//不能定义再里面，不然每次都会新建count
    int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }

    /* 2、子问题的方式求二叉树节点的个数
     * @author zj
     * @date 2022/3/1
     * @param root
     * @return int
     */
    int size2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size(root.right) + size(root.left) + 1;
    }

    /* 获取叶子节点的个数
     * @author zj
     * @date 2022/3/2
     * @param null
     * @return null
     */
    //1、遍历思路：遍历到叶子节点count++
    int leafcount = 0;
    int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            leafcount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafcount;
    }

    //2、子问题思路：左子树的叶子节点加上右子树的叶子节点个数就是总的叶子节点个数
    int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    /* 获取第K层节点的个数
     * @author zj
     * @date 2022/3/2
     * @param root
     * @param k
     * @return int
     */
    int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }

    /* 获取二叉树的高度
     * @author zj
     * @date 2022/3/2
     * @param root
     * @return int
     */
    //子问题思路：左数的高度和右树的高度取最大值，然后+1
    //时间复杂度：O(n)
    //空间复杂度：O(log n)
    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);//最好计算结果记录下来，否则多次计算迭代的次数就过多
        return left > right ? left+1 : right+1;
    }

    /* 检测值为value的元素是否存在
     * @author zj
     * @date 2022/3/2
     * @param root
     * @param val
     * @return test_31.TreeNode
     */
    TreeNode find(TreeNode root, int val) {
        if(root == null) {
            return null;
        }
        if(root.value == val) {
            return root;
        }
        TreeNode ret = find(root.left,val);
        if(ret != null) {
            return ret;
        }
        ret = find(root.right,val);
        if(ret != null) {
            return ret;
        }
        return null;
    }

    /* 判断一棵树是不是完全二叉树
     * @author zj
     * @date 2022/3/2
     * @param root
     * @return boolean
     */
    //1、定义一个队列将根节点入队列再出队并将孩子节点入队，
    //用cur记录出对的元素当cur中的元素为null时判断队列里面是不是全为空，
    //如果全为空则是完全二叉树，如果不全为空就不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        //不能用isEmpty()直接判断的原因是，队列全为null时，返回值也是false，也即队列长度不为0
        while(!queue.isEmpty()) {
            TreeNode top = queue.peek();
            if(top != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }

    /* 检查两棵树是否相同 时间复杂度O(Min(m,n)) m,n分别是p,q的节点个数
     * @author zj
     * @date 2022/3/2
     * @param p
     * @param q
     * @return boolean
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null && q != null || p !=null && q == null) {
            return false;
        }
        if(p.value != q.value) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    //判断一棵树是否为另一棵树的子树
    //1、判断两棵树是否相同
    //2、判断sub是否与root的左子树或者右子树相同  时间复杂度O(m*n)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null) {
            return true;
        }
        if(root == null || subRoot == null) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        //判断子树与subRoot
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;
    }

    /* 判断是否是平衡二叉树 时间复杂度O(n^2)
     * @author zj
     * @date 2022/3/2
     * @param root
     * @return boolean
     */
    //1、root左树和右树的高度差为1
    //2、root的左树和右树都是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    //法2：
    //优化时间复杂度为O(n) 在计算高度的过程中就判断是否平衡
    public int height (TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root == null) {
            return true;
        }
        return height(root) >=0;
    }


    /* 判断一颗二叉树是否对称
     * @author zj
     * @date 2022/3/2
     * @param leftTree
     * @param rightTree
     * @return boolean
     */
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        }
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.value != rightTree.value) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) && isSymmetricChild(leftTree.right,rightTree.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

    /* 已知二叉树前序遍历创建一颗二叉树，并以中序遍历输出
     * @author zj
     * @date 2022/3/2
     * @param str
     * @return test_31.TreeNode
     */
    public int i;
    public TreeNode createTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            //前序的序列 因此创建使用根、左、右
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    //中序遍历
    public  void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.printf(root.value + " ");
        inorder(root.right);
    }

    /* 层序遍历
     * @author zj
     * @date 2022/3/2
     * @param root
     */
    public void levelOrder(TreeNode root)  {
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.println(cur.value+ " ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    //二叉树的层序遍历, 返回二维List
    public List<List<Integer>> levelOrde2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            //因为输出为每一层一个小的数组[]输出
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.value);
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    /* 求两个节点的最近公共祖先
     * @author zj
     * @date 2022/3/2
     * @param root
     * @param p
     * @param q
     * @return test_31.TreeNode
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode leftT = lowestCommonAncestor(root.left,p,q);
        TreeNode rightT = lowestCommonAncestor(root.right,p,q);
        if(leftT != null && rightT != null) {
            return root;
        }else if(leftT != null) {
            return leftT;
        }else {
            return rightT;
        }
    }

    //思路2：孩子双亲的方法存储延申，用两个栈分别存储根到pq的路径，然后再采用链表求交点的思想求最近公共祖先。
    //查找并存储从根节点到指定节点的路径
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null || node == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg) {
            return true;
        }
        flg = getPath(root.right,node,stack);
        if(flg) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int size =  size1 - size2;
            while(size != 0) {
                stack1.pop();
                size--;
            }
            while(!stack1.isEmpty() && !stack2.isEmpty()) {
                if(stack1.peek() == stack2.peek()) {
                    return stack1.pop();
                }else {
                    stack1.pop();
                    stack2.pop();
                }
            }
        }else {
            int size =  size2 - size1;
            while(size != 0) {
                stack2.pop();
                size--;
            }
            while(!stack1.isEmpty() && !stack2.isEmpty()) {
                if(stack1.peek() == stack2.peek()) {
                    return stack1.pop();
                }else {
                    stack1.pop();
                    stack2.pop();
                }
            }
        }
        return null;
    }


    //在中序遍历的过程中将二叉树转化成一个双向链表
    /* 二叉树搜索树转换成排序双向链表
     * @author zj
     * @date 2022/3/3
     * @param null
     * @return null
     */
    TreeNode prev = null;
    public void inorder2(TreeNode pCur) {
        if(pCur == null) {
            return;
        }
        inorder2(pCur.left);
        pCur.left = prev;
        if(prev != null) {
            prev.right = pCur;
        }
        prev = pCur;
        inorder2(pCur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        inorder2(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null) {
            head = head.left;
        }
        return head;
    }

    /* 根据一棵树的前序遍历与中序遍历构造二叉树 buildTree
     * @author zj
     * @date 2022/3/3
     * @param null
     * @return null
     */
    public int preIndex = 0;
    public TreeNode createTreeByPandI(int[] preorder,int[] inorder,int inbegin,int inend) {
        //preorder 前序遍历  inorder 是中序遍历 preIndex 是前序遍历数组的引用，inbegin是中序遍历的前引用，inend是中序遍历的后引用。
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndexOfI(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1) {
            return null;
        }
        preIndex++;
        root.left = createTreeByPandI(preorder,inorder,inbegin,rootIndex-1);
        root.right = createTreeByPandI(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findIndexOfI(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i<= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null) {
            return null;
        }
        return createTreeByPandI(preorder,inorder,0,inorder.length-1);
    }

    //中序加后序遍历
    public int postIndex;
    public TreeNode createTreeByPandI2(int[] inorder,int[] postorder,int inbegin,int inend) {
        //preorder 前序遍历  inorder 是中序遍历 preIndex 是前序遍历数组的引用，inbegin是中序遍历的前引用，inend是中序遍历的后引用。
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndexOfI2(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex == -1) {
            return null;
        }
        postIndex--;
        //先 右子树 后 左子树
        root.right = createTreeByPandI2(inorder,postorder,rootIndex+1,inend);
        root.left = createTreeByPandI2(inorder,postorder,inbegin,rootIndex-1);
        return root;
    }
    private int findIndexOfI2(int[] inorder,int inbegin,int inend,int key) {
        for(int i = inbegin; i<= inend;i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null) {
            return null;
        }
        postIndex = inorder.length - 1;
        return createTreeByPandI2(inorder,postorder,0,inorder.length-1);
    }

    /* 采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串
     * @author zj
     * @date 2022/3/4
     * @param t
     * @param sb
     */
    public void treeToString(TreeNode t,StringBuilder sb) {
        if(t == null) {
            return;
        }
        sb.append(t.value);

        if(t.left != null) {
            sb.append("(");
            treeToString(t.left,sb);
            sb.append(")");
        }else {
            if(t.right == null) {
                return;
            }else {
                sb.append("()");
            }
        }

        if(t.right == null) {
            return;
        }else {
            sb.append("(");
            treeToString(t.right,sb);
            sb.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        treeToString(root,sb);
        return sb.toString();
    }

    /* 非递归实现前序遍历，借助栈来实现
     * @author zj
     * @date 2022/3/4
     * @param root
     */
    void preOrderNor(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                System.out.print(cur.value + " ");
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    /* 中序遍历(非递归)
     * @author zj
     * @date 2022/3/4
     * @param root
     */
    void inOrderNor(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            System.out.print(top.value + " ");
            cur = top.right;
        }
    }

    /* 后序遍历(非递归实现)
     * @author zj
     * @date 2022/3/4
     * @param root
     */
    void postOrderNor(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;

        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            //如果当前节点的右子树被打印过或者遍历过就直接进行弹出就可以了
            if(top.right == null || top.right == prev) {
                stack.pop();
                System.out.print(top.value+ " ");
                prev = top;//记录最近一次打印的节点，防止重复打印，陷入死循环。
            }else {
                cur = top.right;
            }
        }
    }

}
